/*
https://leetcode-cn.com/problems/course-schedule-iii/solution/ke-cheng-biao-iii-by-leetcode-solution-yoyz/
 */
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution630 {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));
        PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->b-a);
        int total=0;
        for (int[] course : courses) {
            if (total+course[0]<=course[1]){
                total+=course[0];
                queue.offer(course[0]);
            }else{
                if (!queue.isEmpty() && queue.peek()>course[0]){
                    total-=queue.poll()-course[0];
                    queue.offer(course[0]);
                }
            }
        }
        return queue.size();
    }

    public static void main(String[] args) {
        System.out.println(new Solution630().scheduleCourse(new int[][]{{100,200},{200,1300},{1000,1250},{2000,3200}}));
    }
}
